package com.cango.student.algorithm;

import java.util.Stack;

/**
 * Function: 三种方式反向打印单向链表
 */
public class ReverseNode {


    /**
     * 利用栈的先进后出特性
     *
     * @param node
     */
    public static void reverseNode1(Node node) {
        if (node == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();

        Node n = node;
        while (n != null) {
            stack.push(n);
            n = n.next;
        }

        while (!stack.isEmpty()) {
            System.out.println(stack.pop().value);
        }

    }


    /**
     * 利用头插法插入链表
     *
     * @param head
     */
    public static void reverseNode(Node head) {
        if (head == null) return;
        Node current = head.next;
        Node pre = head;

        while (current != null) {
            Node next = current.next;

            current.next = pre;

            pre = current;
            current = next;
        }

        head.next = null;
        head = pre;

        //遍历新链表
        while (head != null) {
            System.out.println(head.value);
            head = head.next;
        }
    }


    public static void main(String[] args) {
        Node<Integer> C = new Node<>(3, null);
        Node<Integer> B = new Node<>(2, C);
        Node<Integer> A = new Node<>(1, B);
//        reverseNode1(A);
//        reverseNode(A);
        recNode(A);
    }


    /**
     * 递归
     *
     * @param node
     */
    public static void recNode(Node node) {
        if (node == null) {
            return;
        }

        if (node != null) {
            recNode(node.next);
        }

        System.out.println(node.value + "===>");

    }


    public static class Node<T> {
        public T value;
        public Node<T> next;


        public Node(T value, Node<T> next) {
            this.next = next;
            this.value = value;
        }
    }
}
